#include <cutil.h>
#include "QP_Utility_header.cu"
#include "QP_Utility.cu"
#include "stdlib.h"
#include "string.h"
#include "stdio.h"


#define SORT_BASE 16

void cpu_mergeSort(int2 *R, int rLen, int2 *S, int uLen, int2 *output)
{
	//merge the relation.
	int pR=0;
	int pS=0;
	int cur=0;
	while(pR<rLen && pS<uLen)
	{
		if(R[pR].y<=S[pS].y)
		{
			output[cur]=R[pR];
			pR++;
			cur++;
		}
		else 
		{
			output[cur]=S[pS];
			pS++;
			cur++;
		}
	}
	//the remainder.
	if(pR==rLen)
	{
		while(pS<uLen)
		{
			output[cur]=S[pS];
			pS++;
			cur++;
		}
	}
	if(pS==uLen)
	{
		while(pR<rLen)
		{
			output[cur]=R[pR];
			pR++;
			cur++;
		}
	}
}


void cpu_reSort(int2 *Sorted, int rLen, int2 *unSorted, int uLen, int2 *output)
{
	memcpy(output, Sorted, sizeof(int2)*rLen);
	memcpy(output+rLen, unSorted, sizeof(int2)*uLen);
	qsort(output,(rLen+uLen),sizeof(int2),compareValue);
}

void cpu_sort(int2 *R, int rLen, int2* output)
{
	memcpy(output, R, sizeof(int2)*rLen);
	qsort(output,rLen,sizeof(int2),compareValue);
}


int ckPartition(int2 *R, int rLen, int2* output)
{
	int cur1=0;
	int cur2=rLen-1;
	int cur=0;
	int endValue=R[cur].y;
	output[cur1]=R[cur];
	cur1++;
	for(cur=1;cur<rLen; cur++)
	{
		if(R[cur].y >= endValue)//good
		{
			output[cur1]=R[cur];
			endValue=output[cur1].y;
			cur1++;
		}
		else
		{
			output[cur2]=R[cur];
			cur2--;
		}
	}
	//printf("%d, %d, total, %d\n",cur1,cur2,rLen);
	return cur1;
}

void adaptiveSort(int2 *R, int rLen, int2* output)
{
	if(rLen<SORT_BASE*4)
		cpu_sort(R,rLen,output);
	else
	{
		int2* RTemp=(int2*)malloc(sizeof(int2)*rLen);
		int2* source=R;
		int2* dest=RTemp;
		int alreadySort=0;
		int mid;
		int flag=0;
		while((alreadySort+SORT_BASE)<rLen)
		{
			if(flag==0)
			{
				source=R; dest=RTemp;
				flag=1;
			}
			else
			{
				source=RTemp; dest=R;
				flag=0;
			}
			mid=ckPartition((source+alreadySort),rLen-alreadySort, (dest+alreadySort));
			cpu_mergeSort(dest, alreadySort, (dest+alreadySort), mid, source);
			alreadySort+=mid;
			//checkSorted(source, alreadySort);
			printf("sorted, %d, ",alreadySort);
			
		}
		
		//if(flag==1)//reverse!
		//{
		//	source=R; 
		//}
		//else
		//{
		//	source=RTemp; 
		//}
		if(alreadySort<rLen)
			qsort(source+alreadySort,rLen-alreadySort,sizeof(int2),compareValue);
		cpu_mergeSort(source, alreadySort, (source+alreadySort), rLen-alreadySort, output);

		
	}
}


void cpu_NagaSort(int2 *R, int rLen, int2 *output,int pass, int *I, int *A, int *B, int *C)
{
	
	int i=0;
	for(i=0;i<rLen;i++)
		I[i]=R[i].y;
	//step1, compute the prefix-min from right to left, store in A.
	int tempValue=TEST_MAX;
	int curValue=0;
	for(i=rLen-1;i>=0;i--)
	{
		curValue=I[i];
		A[i]=tempValue;
		tempValue=MIN(tempValue,curValue);
	}
	__DEBUG__(A,rLen);
	//step2, compare I and A, and store the result into B.
	for(i=0;i<rLen;i++)
		if(I[i]<=A[i])
			B[i]=1;
		else
			B[i]=0;
	__DEBUG__(B,rLen);
	//for elements that are zero, compute a prefix min from left to right, store in A.
	tempValue=TEST_MAX;
	curValue=0;
	for(i=0;i<rLen;i++)
	{
		if(B[i]==0)
			curValue=I[i];
		else
			curValue=TEST_MAX;
		A[i]=tempValue;
		tempValue=MIN(tempValue,curValue);
	}
	__DEBUG__(A,rLen);
	//compare I and A, if I[i]<A[i] and B[i]==1, C[i]=1;
	for(i=0;i<rLen;i++)
		if(I[i]<=A[i] && B[i]==1)
			C[i]=1;
		else
			C[i]=0;
	__DEBUG__(C,rLen);
	// Generate a +-scan from left-to-right on C, and store it in A.
	int pSum=0;
	for(i=0;i<rLen;i++)
	{
		A[i]=pSum;
		pSum+=C[i];
	}
	//for the zeros starting at <pSum>
	__DEBUG__(A,rLen);

	int zSum=0;
	for(i=0;i<rLen;i++)
	{
		if(C[i]==0)
		{
			A[i]=pSum+zSum;
			zSum++;
		}
	}
	__DEBUG__(A,rLen);

	//write to output
	for(i=0;i<rLen;i++)
		output[A[i]]=R[i];
	printf("\nsorted****************** %d\n", pSum);
#ifdef DEBUG_SAVEN
	for(i=0;i<pSum;i++)
		printf("%d, ", output[i].y);
#endif
	printf("\nunsorted****************** %d\n", rLen-pSum);
#ifdef DEBUG_SAVEN
	for(i=pSum;i<rLen;i++)
		printf("%d, ", output[i].y);
#endif
	printf("\n one pass is done, %d\n", pass);
	//copy R back to output
	memcpy(R, output, sizeof(int2)*rLen);
	//[1,...,pSum] is sorted.
	pass++;
	if(pSum!=rLen)
	{
		cpu_NagaSort(R+pSum, (rLen-pSum), output+pSum, pass, I, A, B, C);
	}
	
}